package com.leetcode.partition14;

/**
 * @author rkc
 * @date 2022/9/1 9:24
 */
public class LC1370上升下降字符串 {

    private int[] cnts = new int[26];
    private StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        System.out.println(new LC1370上升下降字符串().sortString("spo"));
    }

    public String sortString(String s) {
        for (int i = 0; i < s.length(); i++) cnts[s.charAt(i) - 'a']++;
        while (sb.length() < s.length()) {
            char c = 'a' - 1;
            while (higher(c)) c = sb.charAt(sb.length() - 1);
            c = 'z' + 1;
            while (lower(c)) c = sb.charAt(sb.length() - 1);
        }
        return sb.toString();
    }

    private boolean lower(char c) {
        //选出比c小的字符
        char t = c;
        for (int i = c - 'a' - 1; i >= 0; i--) {
            if (cnts[i] != 0) {
                c = (char) (i + 'a');
                break;
            }
        }
        if (c != t) {
            cnts[c - 'a']--;
            sb.append(c);
            return true;
        }
        return false;
    }

    private boolean higher(char c) {
        char t = c;
        //选出比c大的字符
        for (int i = c - 'a' + 1; i < 26; i++) {
            if (cnts[i] != 0) {
                c = (char) (i + 'a');
                break;
            }
        }
        if (c != t) {
            cnts[c - 'a']--;
            sb.append(c);
            return true;
        }
        return false;
    }
}
